package com.example.system.class25;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Date 2022/8/25
 * @Author Jonathan
 * @Description 滑动窗口问题
 * 假设一个固定大小为W的窗口，依次划过arr，
 * 返回每一次滑出状况的最大值
 * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
 * 返回：[5,5,5,4,6,7]
 */
public class Code01_SlidingWindowMaxArray {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int w = 3;
        final int[] array = slidingWindowMaxArray(arr, w);
        System.out.println(Arrays.toString(array));
    }

    private static int[] slidingWindowMaxArray(int[] arr, int window) {
        LinkedList<Integer> queue = new LinkedList<>();
        int N = arr.length;
        int[] ans = new int[N - window + 1];
        for (int index = 0; index < arr.length; index++) {
            // 弹出比当前元素小的 然后将当前元素加进去
            while (!queue.isEmpty() && arr[queue.peekLast()] < arr[index]) {
                // 这个循环只是移出去了当前小的元素 有可能超出窗口的大的值还在
                queue.pollLast();
            }
            queue.add(index);
            // 对于超出窗口的最大值也需要移出去
            if ((index - queue.peekFirst()) >= window) {
                queue.pollFirst();
            }
            // 清除不在窗口之内的元素
            // index -> index-window+1
            if (index - window + 1 >= 0) {
                // 看一下队列的头元素是谁
                ans[index - window + 1] = arr[queue.peek()];
            }
        }
        return ans;
    }
}
